package _07_adjListGraph;

import _02_singlyLinkedList.Node;
import _02_sortedSinglyLinkedList.SortedSinglyLinkedList;
import _05_linkedMatrix.LinkedMatrix;
import _05_triple.Triple;
import _07_abstractGraph.AbstractGraph;

// 邻接表存储的带权图类，T表示顶点元素类型；继承抽象图类
public class AdjListGraph<T> extends AbstractGraph<T> {
    
    // 图的邻接表，矩阵行的单链表
    protected LinkedMatrix linkmat;
    
    // 构造空图，顶点数为0，边数为0
    public AdjListGraph() {
        // 构造空顶点顺序表，默认容量
        super();
        // 构造0 x 0矩阵，默认容量
        this.linkmat = new LinkedMatrix(0, 0);
    }
    
    // 以vertexes顶点集合构造图，边集合为空
    public AdjListGraph(T[] vertexes) {
        this();
        for (int i = 0; i < vertexes.length; i++) {
            // 插入顶点
            this.insert(vertexes[i]);
        }
    }
    
    // 以vertexes顶点集合和edges边集合构造图
    public AdjListGraph(T[] vertexes, Triple[] edges) {
        this(vertexes);
        for (int i = 0; i < edges.length; i++) {
            this.insert(edges[i]);
        }
    }
    
    @Override
    // 插入元素为的顶点，返回x顶点序号
    public int insert(T x) {
        // TODO Auto-generated method stub
        // 顶点顺序表尾插入x，自动扩容
        this.vertexlist.insert(x);
        // 获得插入顶点x的序号
        int i = this.vertexCount() - 1;
        // 若邻接矩阵容量不够
        if (i >= this.linkmat.rows) {
            linkmat.setRowsColumns(i+1, i+1);
        }
        return i;
    }

    @Override
    // 插入边<vi, vj>，权值为w
    public void insert(int i, int j, int w) {
        // TODO Auto-generated method stub
        // 不能表示自身环
        if (i != j) {
            // 边的权值容错，视为无边，取值0
            if (w < 0 || w > MAX_WEIGHT) {
                w = 0;
            }
            // 设置第i条边单链表中<vi, vj>边的权值为w，若0 < w < ∞，则插入边或替换边的权值
            // 若w == 0，则删除该边，若i、j越界，则抛出序号越界异常
            this.linkmat.set(i, j, w);
        } else {
            throw new IndexOutOfBoundsException("不能插入自身环, i = " + i + ", j = " + j);
        }
    }
    
    // 插入一条边
    public void insert(Triple edge) {
        // TODO Auto-generated method stub
        this.insert(edge.getRow(), edge.getColumn(), edge.getValue());
    }

    // 返回图的顶点集合和邻接表描述字符串
    public String toString() {
        return super.toString() + "出边表：\n" + this.linkmat.toString();
    }
    
    @Override
    // 返回<vi, vj>边的权值，用于图的最小生成树、最短路径等算法
    public int weight(int i, int j) {
        // TODO Auto-generated method stub
        if (i == j) {
            return 0;
        }
        int w = this.linkmat.get(i, j);
        return w == 0 ? MAX_WEIGHT : w;
    }
    
    @Override
    // 删除一条边<vi, vj>，忽略权值
    public void remove(int i, int j) {
        // TODO Auto-generated method stub
        if (i != j) {
            this.insert(i, j, 0);
        }
    }
    
    // 删除一条边
    public void remove(Triple edge) {
        this.linkmat.set(edge.getRow(), edge.getColumn(), 0);
    }
    
    @Override
    // 删除顶点vi及其所有关联的边，返回顶点vi元素。用最后一个顶点替换顶点vi
    public T remove(int i) {
        // TODO Auto-generated method stub
        int n = this.vertexCount();
        if (i >= 0 && i < n) {
            T x = this.vertexlist.get(i);
            // 一、顶点顺序表删除第i个顶点，用最后一个顶点替换顶点vi
            this.vertexlist.set(i, this.vertexlist.get(n-1));
            this.vertexlist.remove(n-1);
            // 二、删除所有与顶点vi向关联的所有边
            // 1、先将第i行用第n-1行替换掉
            this.linkmat.rowlist.set(i, this.linkmat.rowlist.get(n-1));
            // System.out.println(this);
            
            for (int j = 0; j < this.linkmat.rows - 1; j++) {
                for (Node<Triple> p = this.linkmat.rowlist.get(j).head.next; p != null; p = p.next) {
                    // 2、删除所有j为i的边
                    if (p.data.getColumn() == i) {
                        this.remove(p.data);
                    }
                    // 3、把所有j为n-1的边的j改为i
                    if (p.data.getColumn() == n-1) {
                        this.remove(p.data);
                        this.insert(new Triple(p.data.getRow(), i, p.data.getValue()));
                    }
                }
                // System.out.println("第" + j + "行改完之后：");
                // System.out.println(this);
            }
            // 4、此时第i行为<v(n-1), vj>，需要把n-1改为i
            for (Node<Triple> p = this.linkmat.rowlist.get(i).head.next; p != null; p = p.next) {
                this.remove(p.data);
                this.insert(new Triple(i, p.data.getColumn(), p.data.getValue()));
            }
            
            // 5、最后把最后一行删掉
            this.linkmat.rowlist.remove(n-1);
            this.linkmat.rows--;
            
            return x;
        } else {
            throw new IndexOutOfBoundsException("i = " + i); 
        }
    }

    @Override
    // 返回顶点vi在vj后的后继邻接顶点序号，若j = -1，则返回vi的第一个邻接顶点序号；
    // 若不存在后继邻接顶点，则返回-1，
    protected int next(int i, int j) {
        // TODO Auto-generated method stub
        int n = this.vertexCount();
        if (i >= 0 && i < n && j >= -1 && j < n) {
            SortedSinglyLinkedList<Triple> link = this.linkmat.rowlist.get(i);
            Node<Triple> find = link.head.next;
            if (j == -1) {
                return find == null ? -1 : find.data.getColumn();
            }
            Triple tri = new Triple(i, j, 0) {
                @Override
                public boolean equals(Object obj) {
                    if (this == obj) {
                        return true;
                    }
                    if (obj instanceof Triple) {
                        Triple triple = (Triple) obj;
                        return this.getRow() == triple.getRow() && this.getColumn() == triple.getColumn() ? true : false;
                    }
                    return false;
                }
            };
            find = this.linkmat.rowlist.get(i).search(tri);
            return find != null && (find = find.next) != null ? find.data.getColumn() : -1;
        }
        return 0;
    }
    
    @Override
    public void minSpanTree() {
        // TODO Auto-generated method stub
        
    }

    @Override
    public void shortestPath(int i) {
        // TODO Auto-generated method stub
        
    }

    @Override
    public void shortestPath() {
        // TODO Auto-generated method stub
        
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        System.out.println("测试构造方法(T[] vertexes, Triple[] edges)：");
        String[] vertexes = {"A", "B", "C", "D", "E", "F"};
        Triple[] edges = {
                new Triple(0, 1, 1), new Triple(0, 1, 3), new Triple(0, 2, 4), new Triple(0, 2, 0),
                new Triple(2, 1, 4), new Triple(2, 3, 5), new Triple(2, 5, 9),
                new Triple(3, 2, 1), new Triple(3, 5, 4),
                new Triple(4, 3, 2), new Triple(4, 5, 3),
                new Triple(5, 4, 3), new Triple(5, 2, 1), new Triple(5, 3, 2)
                };
        AdjListGraph<String> ag = new AdjListGraph<String>(vertexes, edges);
        System.out.println(ag);
        System.out.println("测试remove(int i)：");
        System.out.println(ag.remove(3));
        System.out.println(ag);
        System.out.println("测试next(int i, int j)：");
        System.out.println(ag.next(3, 3));
        AdjListGraph<String> ag1 = new AdjListGraph<String>(vertexes, edges);
        System.out.println("测试DFSTraverse(int i)：");
        ag1.DFSTraverse(0);
        System.out.println("测试BFSTraverse(int i)：");
        ag1.BFSTraverse(0);
        
    }
}
